package com.zpself.module.算法练习.算法.排序算法;

import com.google.common.collect.Lists;
import org.junit.Test;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author By ZengPeng
 * @Description 参考：https://www.cnblogs.com/MOBIN/p/4681369.html
 * 通过与随机一个元素比较，双指针移动
 * @date in  2021/4/9 11:04
 * @Modified By
 */
public class 快速排序_O_nxlogn {
    @Test
    public void main() {
        int[] arr = new int[]{12, 5, 6, 4, 7, 8, 5, 101, 0, 72};
        myQuickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + ",");
        }
        Arrays.sort(arr);
    }

    private void myQuickSort(int arr[], int _left, int _right) {
        int left = _left;
        int right = _right;
        if (left <= right) {   //待排序的元素至少有两个的情况
            int middle = arr[left];//进来再赋值，防止下标越界
            while (left != right) {
                while (left < right && arr[right] >= middle)
                    right--;
                arr[left] = arr[right];
                while (left < right && arr[left] <= middle)
                    left++;
                arr[right] = arr[left];
            }
            arr[right] = middle;
            myQuickSort(arr, _left, right - 1);
            myQuickSort(arr, right + 1, _right);
        }
    }


    private void quickSort(int arr[], int _left, int _right) {
        int left = _left;
        int right = _right;
        int temp;
        if (left <= right) {   //待排序的元素至少有两个的情况
            temp = arr[left];  //待排序的第一个元素作为基准元素
            while (left != right) {   //从左右两边交替扫描，直到left = right
                while (left < right && arr[right] >= temp)
                    right--;        //从右往左扫描，找到第一个比基准元素小的元素
                arr[left] = arr[right];  //找到这种元素arr[right]后与arr[left]交换
                while (left < right && arr[left] <= temp)
                    left++;         //从左往右扫描，找到第一个比基准元素大的元素
                arr[right] = arr[left];  //找到这种元素arr[left]后，与arr[right]交换
            }
            arr[right] = temp;    //基准元素归位
            quickSort(arr, _left, left - 1);  //对基准元素左边的元素进行递归排序
            quickSort(arr, right + 1, _right);  //对基准元素右边的进行递归排序
        }
    }
}
